#include <iostream>
#include <vector>
using namespace std;


/**
 * @方法: 转换为背包问题
 * @时间复杂度: o()
 * @空间复杂度: o()
 * @评价:
 */
bool dp[10005];
bool canPartition(vector<int>& nums) {
    int sum = 0;
    for (int i = 0; i < nums.size(); i++) sum += nums[i];
    if (sum % 2) return false;
    sum /= 2;
    for (int j = 0; j <= sum; j++) {
        if (nums[0] == j) dp[j] = 1;
    }
    for (int i = 1; i < nums.size(); i++) {
        for (int j = sum; j >= 0; j--) {
            if (j == nums[i])
                dp[j] = 1;
            else if (j > nums[i])
                dp[j] = dp[j - nums[i]] || dp[j];
        }
    }
    return dp[sum];
}